package 代码题.二叉树题目;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * 将一个二叉树转变为它的镜像
 */
public class MirrorBinaryTree {

    /**
     *      8
     *    /  \
     *   6    10
     *   /\    /\
     * 5   7  9  11
     * 在转化为
     * *      8
     *      /  \
     *    10    6
     *   /\    /\
     * 11  9  7  5
     * @param args
     */
    public static void main(String[] args) {
        Node root=new Node(8);
        root.left=new Node(6);
        root.left.left=new Node(5);
        root.left.right=new Node(7);
        root.right=new Node(10);
        root.right.left=new Node(9);
        root.right.right=new Node(11);
        Queue<Node> queue=new ArrayDeque<>();
        print(root);
        System.out.println();
        mirrorTree(root);
        print(root);
        System.out.println();
    }

    public static void print(Node root){
        Queue<Node> queue=new ArrayDeque();
        if(root==null){
            return ;
        }
        queue.add(root);
        while (!queue.isEmpty()){
            Node tmp=queue.poll();
            System.out.print(tmp.val+"\t");
            if(tmp.left!=null){
                queue.add(tmp.left);
            }
            if(tmp.right!=null){
                queue.add(tmp.right);
            }
        }
    }

    /**
     * 思路：层次遍历，然后然后右左入队列
     * @param root
     */
    public static void mirrorTree(Node root){
        Queue<Node> queue=new ArrayDeque();
        if(root==null){
            return ;
        }
        queue.add(root);
        while (!queue.isEmpty()){
            Node tmp=queue.poll();
            if(tmp.left!=null && tmp.right!=null){
                //交换两个节点
                Node t=tmp.left;
                tmp.left=tmp.right;
                tmp.right=t;
            }

            if(tmp.left!=null){
                queue.add(tmp.left);
            }
            if(tmp.right!=null){
                queue.add(tmp.right);
            }
        }
    }

}

class Node{
    int val;
    Node left;
    Node right;

    public Node(int val){
        this.val=val;
    }
}
